package 有序数组的平方;

public class Square_of_ordered_array {
    public static void main(String[] args) {
            /*
            给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

            输入：nums = [-4,-1,0,3,10]
            输出：[0,1,9,16,100]
            解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

             */
    }

    public static int[] sortedSquares(int[] nums){
        // 双指针法
        // 1.平方的最大值一定不会出现在中间，只能出现在数组的两端，那么就可以利用双指针指向数组的两端，不断的寻找当前数组的最大值
        // 2.再顶一个一个result数组，记录平方之后的值

        // 指向数组的左端
        int left = 0;
        // 指向数组的右端
        int right = nums.length - 1;
        // 记录平方之后的数组
        int[] result = new int[nums.length];
        // 记录result数组当前写入的位置
        int k = result.length;

        while ( left <= right ){
            if ( Math.abs(nums[left]) > Math.abs(nums[right]) ) {
                result[k--] = nums[left] * nums[left];
                left++;
            }
            else {
                result[k--] = nums[right] * nums[right];
                right--;
            }
        }
        return result;

    }
}
